package algorithm.difficult;

import java.util.*;

/**
 * 给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。
 * <p>
 * “最近的”定义为两个整数差的绝对值最小。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: n = "123"
 * 输出: "121"
 * 示例 2:
 * <p>
 * 输入: n = "1"
 * 输出: "0"
 * 解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-the-closest-palindrome
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class NearestPalindromic564 {
    /**
     * 考虑到以上所有的可能，我们可以给出最终的方案：分别计算出以下每一种可能的方案对应的回文整数，在其中找到与原数最近且不等于原数的数即为答案。
     * <p>
     * 1.用原数的前半部分替换后半部分得到的回文整数。
     * <p>
     * 2.用原数的前半部分加一后的结果替换后半部分得到的回文整数。
     * <p>
     * 3.用原数的前半部分减一后的结果替换后半部分得到的回文整数。
     * <p>
     * 4.为防止位数变化导致构造的回文整数错误，因此直接构造 999…999 和 100…001 作为备选答案。
     * 如：100-99   999->1001
     * <p>
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/find-the-closest-palindrome/solution/xun-zhao-zui-jin-de-hui-wen-shu-by-leetc-biyt/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param n
     * @return
     */
    public String nearestPalindromic(String n) {
        List<Long> allNums = getAllNums(n);
        long self = Long.parseLong(n);
        long ans = -1;
        for (Long l : allNums) {
            if (l != self) {
                if (ans == -1 ||
                        Math.abs(l - self) < Math.abs(ans - self) ||
                        Math.abs(l - self) == Math.abs(ans - self) && l < ans) {
                    ans = l;
                }
            }
        }
        return String.valueOf(ans);
    }

    public List<Long> getAllNums(String n) {
        ArrayList<Long> list = new ArrayList<>();
        //得到情况4。
        list.add((long) Math.pow(10, n.length()) + 1);
        list.add((long) Math.pow(10, n.length() - 1) - 1);
        //得到情况1，2，3
        long preNum = Long.parseLong(n.substring(0, (n.length() + 1) / 2));
        for (long i = preNum - 1; i <= preNum + 1; i++) {
            StringBuilder stringBuilder = new StringBuilder();
            String preString = Long.toString(i);
            stringBuilder.append(preString);
            StringBuilder reverse = new StringBuilder(preString).reverse();
            stringBuilder.append(reverse.substring(n.length() & 1));
            list.add(Long.parseLong(stringBuilder.toString()));
        }
        return list;
    }

}
